#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 1000, MAXM = 1000000, INF = 10001000;
int n = 9, m = 28; // |V|=n, |E|=m
int u[MAXM] = {0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 ,1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 };
int v[MAXM] = {1,2,2 ,3,8,4,3,4,5,6,6,6 ,7,7 ,0,0,1 ,1,2,2,8,8,3,3,4,5 ,5,6 };
int w[MAXM] = {4,8,11,8,7,1,2,6,7,4,2,14,9,10,4,8,11,8,7,1,2,6,7,4,2,14,9,10};
int d[MAXN][MAXN];

void Floyd() {
    for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
        d[i][j] = (i == j) ? 0 : INF;
    for (int e = 0; e < m; ++e) {
        int x = u[e], y = v[e];
        d[x][y] = min(d[x][y], w[e]); //prevent self loop
    }
    for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

int main() {
    Floyd();
    for (int i = 0; i < n; ++i) cout << d[0][i] << ' ';
    cout << endl;
}

